#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 广度优先搜索
# 广度优先搜索用于在非加权图中查找最短路径
# 
# 有向图:
# A->B , A->C , B->F , C->D , C->E , D->F , E->F , F->G 
#
#     B ----- F
#   /       / |
# A       D   |
#   \   /     |
#     C ----- E --- G
#
#
# 如果需要把路径输出，需要把父节点带上。

from collections import deque

start_node = 'A'
target_node = 'F'

# 生成图字典
graph = {}
graph['A'] = ['B', 'C']
graph['B'] = ['F']
graph['C'] = ['D', 'E']
graph['D'] = ['F']
graph['E'] = ['F', 'G']
graph['F'] = []
graph['G'] = []


# 广度优先搜索, start 是起点
def BFS_Search(start):
    search_queue = deque() # 创建待查询节点队列
    search_queue += graph[start] # 往查询队列插入 起点start 的邻居节点
    exist_queue = deque() # 已经查询过的节点队列
    
    while search_queue: # 只要队列不为空就处理
        node = search_queue.popleft() # 从队列中左移出一个节点
        if node not in exist_queue: # 如果该节点没有查询过，则进行处理
            if node_is_target(node): # 判断是否目标节点
                print('find the path from [%s] to [%s]' % (start, node))
                return True
            else:
                search_queue += graph[node] # 将查询节点的邻居节点加入队列
                exist_queue.append(node) # 将节点标记为已处理
    print('cant find the path from [%s] to [%s]' % (start, node))
    return False
    
# 判断是否目标节点
def node_is_target(node):
    return node == target_node


if __name__=='__main__':
    BFS_Search(start_node)
    
